package lanQiaoBei.搜索与图论.最短路.dijkstra;
import java.io.*;
import java.util.*;
import java.math.*;
/*堆优化版的dijkstra
题目描述
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

输入格式
第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

输出格式
输出一个整数，表示1号点到n号点的最短距离。

如果路径不存在，则输出-1。

数据范围
1≤n,m≤105,
图中涉及边长均不超过10000。

样例
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
* */
public class P2 {//边与点的数量大致相等使用临接表存储
       static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       final static int N=100010;
       static int h[]=new int[N],e[]=new int[N],ne[]=new int[N],w[]=new int[N],dist[]=new int[N],n,m,idx;
       static boolean close[]=new boolean[N];
       static void add(int a,int b,int c){
              e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
       }
       static void scan()throws Exception{
              String[]ss=br.readLine().split(" ");
              n=Integer.parseInt(ss[0]);m=Integer.parseInt(ss[1]);

              Arrays.fill(h,-1);
              while(m-->0){
                   ss=br.readLine().split(" ");
                   add(Integer.parseInt(ss[0]),Integer.parseInt(ss[1]),Integer.parseInt(ss[2]));
              }
       }
       static int dijkstra(){
              Arrays.fill(dist,0x3f3f3f3f);
              dist[1]=0;
              PriorityQueue<Pair>q=new PriorityQueue();
              q.add(new Pair(1,0));
              while(q.size()>0){
                  Pair t = q.poll();
                  int dot=t.first,distance=t.second;
                  if(close[dot])continue;
                  close[dot]=true;

                  for(int i=h[dot];i!=-1;i=ne[i]){
                      int j=e[i];
                      if(w[i]+distance<dist[j]){
                          dist[j]=distance+w[i];
                          q.add(new Pair(j,dist[j]));
                      }
                  }
              }
              if(dist[n]==0x3f3f3f3f)return -1;
              else return dist[n];
       }
       public static void main(String[]args)throws Exception{
               scan();
               System.out.print(dijkstra());
       }
       static class Pair implements Comparable<Pair>{
              int first;int second;
              Pair(int f,int s){
                  first=f;
                  second=s;
              }
           @Override
           public int compareTo(Pair o) {
               Pair p=(Pair)o;
               return p.second-this.second;
           }
       }
}
